package me.timlong;

import java.util.ArrayList;

public class JumpingFrog {

    /**
     * 题目描述
     * 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
     *
     * @param target
     * @return
     */

    public int JumpFloor(int target) {

        //面试的高效算法
        /**
         * f(n) = 1, n = 1; 2, n = 2; f(n-1) + f(n-2), n > 2
         *  (1, ) 1, 2, 3, 5, 8
         *
         *
         */
        int a = 1, b = 1;
        for(int i = 2; i <= target; i++){
            a = a + b;
            b = a - b;
        }
        return a;
    }

    /**
     *题目描述
     * 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。
     * 求该青蛙跳上一个n级的台阶总共有多少种跳法。
     *
     * 解决方案：
     *
     * 设n 级台阶有f(n)f(n) 种跳法，根据最后一次跳台阶的数目可以分解为最后一次一级，则前面需要跳n-1级，有f(n-1) 种跳法；最后一次跳两级，则前面需要跳n- 2n−2 级，有f(n-2)f(n−2) 种跳法。以此类推 易知，
     * f(n)=f(n-1)+f(n-2)+……f(0)
     * f(n-1)=f(n-2)+……f(0)
     * 两式相减得，
     *
     * f(n)=2f(n-1)
     *
     * @param target
     * @return
     */
    public int JumpFloorII(int target) {
        if(target <= 0)
            return 0;

        ArrayList<Integer> ls = new ArrayList<>();
        ls.add(0, 0);
        ls.add(1, 1);
        for(int i = 2; i <= target; i++)
            ls.add(i, ls.get(i - 1) * 2);

        return ls.get(target);
    }



    public static void main(String[] args) {
//        System.out.println(new JumpingFrog().JumpFloor(5));

        System.out.println(new JumpingFrog().JumpFloorII(6));
    }
}
